// https://leetcode.cn/problems/multiply-strings/description/

// 算法思路总结：
// 1. 模拟竖式乘法计算字符串表示的大数乘法
// 2. 反转字符串从低位到高位处理
// 3. 使用临时数组存储每位乘积结果
// 4. 统一处理进位生成最终结果字符串
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m+n)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    string multiply(string num1, string num2) 
    {
        if (num1 == "0" || num2 == "0")
        {
            return "0";
        }

        int m = num1.size(), n = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        vector<int> tmp(m + n - 1, 0);
        for (int i = 0 ; i < m ; i++)
        {
            for (int j = 0 ; j < n ; j++)
            {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        string res;
        int carry = 0, cur = 0;
        while (cur < m + n - 1 || carry)
        {
            if (cur < m + n - 1) 
            {
                carry += tmp[cur++];
            }
            res += (carry % 10 + '0');
            carry /= 10;
        }
        reverse(res.begin(), res.end());

        return res;
    }
};

int main()
{
    string n11 = "2", n12 = "3";
    string n21 = "123", n22 = "456";

    Solution sol;

    cout << sol.multiply(n11, n12) << endl;
    cout << sol.multiply(n21, n22) << endl;

    return 0;
}